package xianchengpool;

import edu.princeton.cs.algs4.In;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

/**
 * @功能
 * @创建时间 2019/12/26
 */
public class T13_ForkJoinPool {

    static List<List<Integer>> lists = new ArrayList<>();;
    static {
        lists.add(new ArrayList<Integer>(){{
            add(1);
            add(2);
            add(5);
            add(7);
        }});
        lists.add(new ArrayList<Integer>(){{
            add(2);
            add(3);
            add(5);
            add(7);
            add(9);
        }});
        lists.add(new ArrayList<Integer>(){{
            add(1);
            add(2);
            add(5);
            add(7);
        }});
//        lists.add(new ArrayList<Integer>(){{
//            add(2);
//            add(3);
//            add(5);
//            add(7);
//            add(9);
//        }});

    }

  static class AddTask extends RecursiveTask<List<Integer>> {
    Integer left, right;

    AddTask(Integer l, Integer r) {
        left = l;
        right = r;
    }

    @Override
    protected List<Integer> compute() {
        //如果有序数组有两个则进行归并
        if (right - left == 1) {
            List<Integer> lleft = lists.get(left);
            List<Integer> lright = lists.get(right);
            return www(lleft,lright);
        }
        //一个有序数组直接返回
        if (right - left == 0) {
            List<Integer> lright = lists.get(right);
            return lright;
        }
        //超过两个则fork子线程进行归并
        int middle = left + (right - left) / 2;
        AddTask subTask1 = new AddTask(left, middle);
        AddTask subTask2 = new AddTask(middle + 1, right);
        subTask1.fork();
        subTask2.fork();
        return www(subTask1.join(),subTask2.join());
    }
    //归并逻辑
    private static List<Integer> www( List<Integer> lleft,List<Integer> lright){
        List<Integer> res = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < lleft.size()  && j < lright.size()){
            if (lleft.get(i) <= lright.get(j)){
                res.add(lleft.get(i));
                i ++;
                continue;
            }else {
                res.add(lright.get(j));
                j++;
                continue;
            }
        }
        while (i < lleft.size() ){
            res.add(lleft.get(i));
            i ++;
            continue;
        }
        while (j < lright.size() ){
            res.add(lright.get(j));
            j++;
            continue;
        }
        return res;
    }
}
    public static void main(String[] args) throws IOException {
        ForkJoinPool f = new ForkJoinPool();
        AddTask task = new AddTask(0,lists.size() - 1);
        f.execute(task);
        List<Integer> result = task.join();
        System.out.println(result);
    }
}
